home *** CD-ROM | disk | FTP | other *** search
/ MacFormat España 13 / MacFormat n. 13 (Spain) / Macformat 13.bin / Shareware Internet / Newton / life-14 folder / life.txt < prev    next >
Encoding:
Text File  |  1996-01-01  |  13.1 KB  |  340 lines
  1. life.txt
  2. S. Weyer
  3. 1/1/96
  4.  
  5. Life is a mathematical simulation game described by John Conway in
  6. Scientific American in Oct. 1970.
  7.  
  8. Several rules are used to create a next generation from a cell's 8 neighbors:
  9. - Survival: A cell with 2 or 3 neighbors survives.
  10. - Death: A cell with 1 or less, or 4 or more neighbors, "dies".
  11. - Birth: An empty cell with exactly 3 neighbors will be "born".
  12.  
  13. Keywords: Life, cellular automata, Newt, mathematical simulation, Conway
  14.  
  15.  
  16. Recent changes [Life 1.4] (1/1/96):
  17. - NOS 2.0 compatible
  18. - integrates 6 display/speed options (selectable via "method" picker)
  19.   2 different representations: array or bitmap
  20.   3 different styles: object-oriented, inline, native(RISC) code
  21. - adds "gen" picker for disabling gen# update or doing timing
  22. - line gesture to fill area, scrub gesture to erase area
  23. - created with Newt Development Environment
  24. - includes Newt source
  25.  
  26. Contents:
  27. - life.txt   -- this file
  28. - Life14.pkg -- a ready-to-install package (created by Newt)
  29. - life.nwt   -- Newt source
  30. - life.bit   -- LifeIcon
  31. (Mac format text file in .sit/.hqx archives; DOS text in .zip archive)
  32.  
  33. The "game of Life" is freeware and may be distributed freely as long as all of
  34. these files are included and unmodified.  You are free to make modifications
  35. for your own use. Copyright 1994-96, S. Weyer. All Rights Reserved Worldwide.
  36.  
  37. ----------
  38. Development and "Newt"
  39.  
  40. If you would like to construct and modify Life directly on your Newton,
  41. obtain the latest version of
  42.  
  43. - "Newt" (newt-devenv-32)  -- an environment for developing applications
  44.   saving as packages directly on your Newton
  45.  
  46. - "Slurpee" (slurpee-17) a text/data transfer utility (both shareware)
  47.  
  48. from your favorite Newton server/archive (internet (AMUG, uiowa,...), AOL,
  49. Compuserve, eWorld). See "Develop" and "Author" help pages. Contact me if you
  50. have trouble finding Newt, using it initially, or have questions about
  51. registering it.
  52.  
  53. Registered Newt users receive a 80+ pp. introductory manual, and access to
  54. 190+ examples. This includes NewtPFB (an interactive tutorial, similar to
  55. NewtATut), and LifeCnst.pkg plug-in for building versions of Life with
  56. native code.
  57.  
  58. For more development details, see "Building and Transferring Life" (later).
  59.  
  60. ----------
  61. Revision History:
  62. Life 1.4 (1/1/96)
  63.   (see above)
  64.  
  65. Life 1.3N & life13.nwt (8/11/95) [non-public releases]
  66. - [very similar to Life 1.2B & life12b1.nwt -- available earlier to Newt users]
  67. - faster generation from native code for several methods
  68. - for increased speed, suppress Gen: refresh by tapping on it
  69.  
  70. Life 1.2B (11/12/94)
  71. - limits width of universe to 30 (width of NewtonScript integer)
  72. - caches/operates on rows as longint (or NIL) rather than bitmap directly
  73. - inlines inner-loop getCell accesses for greater speed (vs. clarity)
  74. - does not display the empty border columns/rows
  75. - numbers x (bit) positions from right to left
  76. - handles scrub gesture for Clear (see LifeDraw:viewGestureScript)
  77. - selectable grid sizes (see gridSize)
  78. - generates faster (1.5 - 3.5x Life 1.2) and allows larger grids
  79.   by using a bitmap data structure for storage and drawing
  80.  
  81. Life 1.2 (11/12/94)
  82. - modifies symbol names/program structure to be more consistent with 1.2B
  83. - fixes button highlighting glitch (sibling order)
  84.  
  85. Life 1.1 (10/15/94)
  86. - uses 0/1 for cell values rather than nil/true
  87. - allows patterns to be selected/added
  88. - adds a grid (when stopped)
  89.  
  90. Life 1.0 (9/18/94)
  91. - adds a "Clear" and "Next" button
  92. - adds a generation counter.
  93. - adds a "Repeat" button -- which invokes "Next" in the background until
  94.   you tap "Stop" (or all cells are empty)
  95. - adds an "Info" button and help book
  96. - avoids allocating/examining empty rows/columns where possible to
  97.   improve speed drawing and generating
  98.  
  99. Life "0.1" (3/94)
  100. - see "Life with NewtonScript" by David Betz in Byte, March 1994, pp. 191-194.
  101. This article provided inspiration, an initial framework and a few main methods.
  102.  
  103. The early versions are quite usable for small patterns, but not blindingly
  104. fast for more sparse or spreadout patterns -- the emphasis is on the complete
  105. application and learning programming.  There is also another source version
  106. life12b.nwt (available to registered Newt users) which is uses the same basic
  107. bitmap representation as life13.nwt, but is slower and perhaps more
  108. understandable since it is less heavily optimized).
  109.  
  110. Possible future enhancements:
  111. - allow patterns to be saved in/retrieved from a soup
  112. - save preferences for grid size, etc.
  113.  
  114. If you would like to encourage me to develop and distribute this and other
  115. examples, I encourage you to register Newt (kind words also appreciated).
  116.  
  117. ----------
  118. Using Life
  119.  
  120. Tap the info button to access the built-in help book.
  121.  
  122. Some classic patterns to try (some in pattern picker):
  123.   OOO     (blinker -- flips)
  124.  
  125.    O
  126.   O       (glider -- moves down&left 1 in 4 steps)
  127.   OOO
  128.  
  129.   OO
  130.   OO      (block -- stable)
  131.  
  132.    OO
  133.   O  O    (beehive -- stable)
  134.    OO
  135.  
  136.     
  137.   OOOOO   (turns into "traffic lights" (4 blinkers) in 9 steps)
  138.  
  139.  OOOOOOO  (turns into "honey farm" (4 beehives) ...)
  140.  
  141. OOOOOOOOO (double traffic lights...)
  142.  
  143. ----------
  144. Transferring and Building Life
  145.  
  146. Use your favorite transfer mechanism to move the text from your desktop system
  147. to the Newton Notepad. This file is formatted to be used most easily with
  148. Slurpee.  ----- delimits separate notes.
  149.  
  150. To build the Life application, install Newt (3.2 is the latest version at
  151. time of this release). If you would like to save the application as the
  152. package to run it standalone later, also install the NewtPack plug-in, which
  153. comes with Newt. If you would like to use native (faster) methods for Life
  154. in Newt, install the LifeCnst.pkg plugin -- this way you could customize the
  155. application while also gaining extra performance by borrowing those methods
  156. from the Life "library". [LifeCnst available to registered Newt users]
  157.  
  158. If you would like to use the Life icon, transfer the life.bit file with Slurpee,
  159. and uncomment the line inside _package in the life.nwt source.
  160.  
  161. Start Newt, select the folder at top where you stored the source.
  162.  
  163. If you are low on heap, you may want to "comment out" the two long in-line
  164. methods: Life._arrI.nextGeneration and Life.bitI.nextGeneration
  165. by changing the names, e.g.,
  166.   xLife._arrI.nextGeneration
  167.   xLife._bitI.nextGeneration
  168. (this will remove them from the build process, and Life will just
  169. use the generic nextGeneration method)
  170. (when you're done, browse to #newObject to free up a little more space)
  171.  
  172. Tap Expr, select :doObj('build,'Life), tap Eval
  173.  
  174. Some simple modifications you might try:
  175. - add other patterns in patternPicker.patterns array (and names in labelCommands)
  176. - add other pages to the helpbook
  177. - change MakeOval to MakeRect in drawDots
  178. - change the rules (nextGeneration)
  179.  
  180. Note: constants such as vfFillWhite can be used, but this requires additional
  181. plug-ins, e.g., viewCnst.pkg to define these at development time.
  182.  
  183. If you would like to run your version of the Life application later without
  184. having to recompile the sources in Newt, and you have NewtPack installed,
  185. tap the Save button (in Eval Controls) when Life is open. (or Eval 
  186. :saveApp(Life)).
  187.  
  188. If you have further optimizations that you would like to contribute, feel free
  189. to send them to me, and if I incorporate them, you'll be recognized.
  190.  
  191. ----------
  192. Implementation:
  193.  
  194. This version of Life show several different implementations.
  195. There are two basic mechanisms: "arr" and "bit".
  196. - "arr" refers to the internal representation of rows as arrays of cells;
  197. the drawing is done cell-by-cell. [similar to an earlier version -- Life 1.2,
  198. and to Betz' Byte article].
  199. - "bit" refers to the internal representation of rows as words in a bitmap;
  200. the drawing is done directly with the bitmap. [similar to Life 1.2B].
  201.  
  202. There are three variations for each: "", "I", "N",
  203. - "".  default. more object-oriented -- uses same :nextGeneration method
  204. - "I". Inline. :nextGeneration inlines (i.e., substitutes definitions for)
  205.   :getCell,:getRow, :setCell,:setRow methods
  206. - "N". Native. :nextGeneration is native (RISC) compiled code.
  207.   For development, this requires you install the LifeConst.pkg plug-in so that you
  208.   can use/copy the constants while still modifying the main application on your Newton
  209.  
  210. So, the source supports 6 versions:
  211. - "arr" uses arrays for representing rows; it is written in a very object-oriented style;
  212.   in fact, it uses the same :nextGeneration method as "bitO".
  213. - "arrI" same as "arr" but in-lines :nextGeneration
  214.   (i.e., substitutes definitions for :getCell,:getRow, :setCell,:setRow methods).
  215. - "arrN" uses native code for :nextGeneration
  216. - "bit" uses a bitmap for representing and drawing cells.
  217.   it uses the same generic :nextGeneration method as "arrO"
  218. - "bitI" same as "bit" but inlines :nextGeneration
  219. - "bitN" uses native code for :nextGeneration and :makeUniverse
  220.    (the NewtonScript is identical to "bitI" but without declarations;
  221.    I did not include the declarations here -- although they are ignored
  222.    by the Newton compiler for NOS 2.0, the 1.x compiler generates errors).
  223.  
  224. The Life application and package was created entirely with the Newt
  225. Development Environment. (LifeCnst.pkg plug-in was created with NTK).
  226.  
  227. ----------
  228.  
  229. Objects:
  230.  
  231. Life -- the application (floating view)
  232.   [split into several sections to make editing on Newton more manageable]
  233. drawArea -- an embedded view to handle drawing
  234. titleObj -- title at top of Life view
  235. status -- status bar at bottom of Life view
  236. clearButton, nextButton, repeatButton, zhelpButton -- embedded in status
  237. gridPicker -- picker for selecting grid size
  238. methPicker -- picker for switching between various "arr" and "bit" methods
  239. patternPicker -- picker for selecting patterns
  240. genPicker -- picker for update/timing, generation counter
  241. helpBook -- help book data structure
  242. helpView -- dynamic "Tiny Tim" help reader view
  243. ButtonBounds -- development-time method for computing location of status buttons
  244.  
  245. "method frames"
  246. there are 6 frames that contain 9 methods each that define the representation,
  247. computation and display for the six versions included: "arr", "arrI", "arrN", "bit", "bitI", "bitN".
  248. when the user makes a choice in "method picker", these are copied into the current
  249. Life application (view). [original "arr" defs are still in the app template]
  250.  
  251. Generally, there are many ways to write "nextGeneration". I chose one that
  252. hopefully isn't too hard to follow, works for both the array and bitmap
  253. representations, and performs reasonably well. With some INT declarations
  254. put in, the same version produces "bitN" which is quite fast.  I would be
  255. interested in any faster algorithms or programming tricks also. (see "Timing"
  256. below).
  257.  
  258. -----
  259. Coordinates:
  260.  
  261. To maximize performance for the "bit" implementation, I constrained the x
  262. coordinate to be between 0 and 29 (numbered from right to left), to
  263. correspond to bit positions in a NewtonScript integer ("long"); the "array"
  264. implementation follows these conventions also in order to share methods. I
  265. have other implementations that can access multiple longs, but large grids
  266. are difficult to display and impractical to compute anyway.  The y
  267. coordinate is numbered from top to bottom. Cells are square.
  268.  
  269. -----
  270.  
  271. You can speed up computation somewhat by selecting "gen <0>".
  272. This indicates that the generation counter should not be updated.
  273.  
  274. -----
  275. Benchmarks
  276.  
  277. To do benchmarks, I would recommend saving the application first. This
  278. maximizes the amount of heap that is available (and minimize the amount
  279. of time that Life spends in gc (garbage collection)).
  280.  
  281. In order to see timing results printed, do one of the following:
  282. - connect the NTK Inspector
  283. - open Slurpee (in Inspect? mode) with a terminal emulator
  284.   [you can drag Slurpee off right screen edge; also toward bottom
  285.   so it's not totally on grid]
  286. - open Newt (and turn on Print?)
  287.  
  288. Select "gen <time:40>" to do 40 iterations of a pattern.
  289.  
  290. Draw your pattern, tap Repeat.
  291.  
  292. time: <ticks = 60ths of a sec> will appear.
  293.  
  294. note: generation counter is set to 0
  295. after Clear, new method picked, or timing complete
  296.  
  297.  
  298. Two simple patterns that indicate roughly the performance profiles
  299. of these different methods.
  300.  
  301. - glider. small dynamic pattern
  302.  
  303. - 4 blocks (one in each corner of grid). maximize number of rows examined
  304.  
  305.  
  306. I used a 26x29 grid. I did two tests for each data point and took the
  307. average. I tested on a MP100(1.3), MP110(1.3) and MP120(2.0).
  308.  
  309.                                             xx    ...    xx
  310.                                             xx        xx
  311.                  x                            ...        
  312.                 x                            xx        xx
  313.                 xxx                            xx        xx
  314.                 glider                        corners4                                
  315.  
  316.         100        110        120            100        110        120
  317.         ----    ----    ----        ----    ----    ----
  318. arr        1100    1030     472        3775    3700    1058
  319. arrI     785     750     385        2374    2330     683
  320. arrN      575     520     405        1336    1320     708
  321. bit      930     940     362        3760    3575     962
  322. bitI     695     682     284        2487    2345     573
  323. bitN     237     215     213         243     220     216
  324.  
  325.  
  326. Some initial observations:
  327. (of course, it's dangerous to draw any very general conclusions
  328. based on such few data points; your mileage may vary depending on
  329. the patterns you try, amount of heap, etc.):
  330.  
  331. - large patterns generally take much longer time (though bitN is almost constant)
  332. - the NOS 2.0 NewtonScript interpreter can be much (2x-3x) faster than 1.x
  333. - some native code (arrN) can be slower on 2.0! (an anomaly worth investigating)
  334.   advantage of bitN much less on 2.0
  335. - MP100 a little slower than MP110
  336.  
  337. I'd be interested in other results/observations on these and
  338. other algorithmic variations.
  339.  
  340.